The ground-state energy of the ±J sping glass. A comparison of various biologically motivated algorithms

We compare various evlutionary strategies to determine the ground-state energy of the ±J spin glass. We show that the choice of different evolution laws is less important than a suitable treatment of the free spins of the system At least one combination of these strategies does not give the correct results, but the ground states of the other different strategies coincide. Therefore we are able to extrapolate the infinit-size ground-state energy for the square lattice to –1.401±0.0015 and for the simple cubic lattice to –1.786±0.004.     

Local minima of the trust region problem

We consider the minimization of a quadratic formzVz+2zq subject to the two-norm constraint z=. The problem received considerable attention in the literature, notably due to its applications to a class of trust region methods in nonlinear optimization. While the previous studies were concerned with just the global minimum of the problem, we investigate the existence of all local minima. The problem is approached via the dual Lagrangian, and the necessary and sufficient conditions for the existence of all local minima are derived. We also examine the suitability of the conventional numerical techniques used to solve the problem to a class of single-instruction multiple-data computers known as processor arrays (in our case, AMT DAP 610). Simultaneously, we introduce certain hardware-oriented multisection algorithms, showing their efficiency in the case of small to medium size problems.This research was partially supported by the National Physical Laboratories of England under Contract RTP2/155/127.     

Convolution semigroups and central limit theorem associated with a dual convolution structure

We consider hypergroups associated with Jacobi functions ⁽⁾ (x), (–1/2). We prove the existence of a dual convolution structure on [0,+[i(]0,s ₀]{{) =++1,s ₀=min(,–+1). Next we establish a Lévy-Khintchine type formula which permits to characterize the semigroup and the infinitely divisible probabilities associated with this dual convolution, finally we prove a central limit theorem.     

Trigonometric wavelets for Hermite interpolation

The aim of this paper is to investigate a multiresolution analysis of nested subspaces of trigonometric polynomials. The pair of scaling functions which span the sample spaces are fundamental functions for Hermite interpolation on a dyadic partition of nodes on the interval . Two wavelet functions that generate the corresponding orthogonal complementary subspaces are constructed so as to possess the same fundamental interpolatory properties as the scaling functions. Together with the corresponding dual functions, these interpolatory properties of the scaling functions and wavelets are used to formulate the specific decomposition and reconstruction sequences. Consequently, this trigonometric multiresolution analysis allows a completely explicit algorithmic treatment.

     

Heuristic methods for evolutionary computation techniques

Evolutionary computation techniques, which are based on a powerful principle of evolution—survival of the fittest, constitute an interesting category of heuristic search. In other words, evolutionary techniques are stochastic algorithms whose search methods model some natural phenomena: genetic inheritance and Darwinian strife for survival.Any evolutionary algorithm applied to a particular problem must address the issue of genetic representation of solutions to the problem and genetic operators that would alter the genetic composition of offspring during the reproduction process. However, additional heuristics should be incorporated in the algorithm as well; some of these heuristic rules provide guidelines for evaluating (feasible and infeasible) individuals in the population. This paper surveys such heuristics and discusses their merits and drawbacks.An abridged version of this paper appears in the volume entitled META-HEURISTICS: Theory & Application, edited by Ibrahim H. Osman and James P. Kelly, to be published by Kluwer Academic Publishers in March 1996.     

Chains of strongly non-reflexive dual groups of integer-valued continuous functions

Answering a question of Eklof-Mekler (Almost free modules, set-theoretic methods, North-Holland, Amsterdam, 1990), we prove: (1) If there exists a non-reflecting stationary set of consisting of ordinals of cofinality for each , then there exist abelian groups such that and for each . (2) There exist abelian groups such that for each and for each . The groups are the groups of -valued continuous functions on a topological space and their dual groups.

     

Nonmonotone bundle-type scheme for convex nonsmooth minimization

In this paper, we present a general scheme for bundle-type algorithms which includes a nonmonotone line search procedure and for which global convergence can be proved. Some numerical examples are reported, showing that the nonmonotonicity can be beneficial from a computational point of view.This work was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell' Universitá e della Ricerca Scientifica e Tecnologica and by ASI: Agenzia Spaziale Italiana.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.     

Analysis of grid file algorithms

Grid file algorithms were suggested in [12] to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. We provide an asymptotic analysis. The growth of the indexes appears to be non-linear for uniform distributions:O(v ^c ) orO(v ), wherec=1+b^–1, =1+(s-1)/(sb+1),s is the number of attributes being used,v the file size, andb the page capacity of the system. Finally we give corresponding results for biased distributions and compare transient phases.